import BinarySearchTree from './binary-search-tree';
import { ICompareFunction, defaultCompare, Compare } from '../util';
import { RedBlackNode, Colors } from './models/red-black-node';

/**
 * 红黑树(RBT)是自平衡树的一种变体，它的左右子树高差有可能大于1（不一定要达到
 * AVL式的平衡），所以它不是严格意义上的自平衡树。红黑树进行平衡的代价较低，
 * 其平均统计性能要强于AVL。（多增删少搜索用RBT，反之用AVL）
 */
export default class RedBlackTree<T> extends BinarySearchTree<T> {
    protected _root: RedBlackNode<T> = null;
    constructor(compareFn: ICompareFunction<T> = defaultCompare) {
        super(compareFn);
    }
    /**
     * 右旋
     *       b                           a
     *      / \                         / \
     *     a   e -> rotationLL(b) ->   c   b
     *    / \                             / \
     *   c   d                           d   e
     */
    private rotationLL(node: RedBlackNode<T>): RedBlackNode<T> {
        const tmp = node.left;
        // 先让tmp与node的父节点联系起来
        if (node.parent == null) {
            this._root = tmp;
        } else if (node.parent.left === node) {
            node.parent.left = tmp;
        } else if (node.parent.right === node) {
            node.parent.right = tmp;
        }
        tmp.parent = node.parent;

        // 再让tmp的右节点移到node的左节点上，并更新parent
        node.left = tmp.right;
        if (tmp.right != null) {
            tmp.right.parent = node;
        }

        // 最后让node作为tmp的右节点，并更新parent
        tmp.right = node;
        node.parent = tmp;
        return tmp;
    }

    /**
     * 左旋
     *
     *     a                              b
     *    / \                            / \
     *   c   b   -> rotationRR(a) ->    a   e
     *      / \                        / \
     *     d   e                      c   d
     */
    private rotationRR(node: RedBlackNode<T>): RedBlackNode<T> {
        const tmp = node.right;
        // 先让tmp与node的父节点联系起来
        if (node.parent == null) {
            this._root = tmp;
        } else if (node.parent.left === node) {
            node.parent.left = tmp;
        } else if (node.parent.right === node) {
            node.parent.right = tmp;
        }
        tmp.parent = node.parent;

        // 再让tmp的左节点移到node的右节点上，并更新parent
        node.right = tmp.left;
        if (tmp.left != null) {
            tmp.left.parent = node;
        }

        // 最后让node作为tmp的左节点，并更新parent
        tmp.left = node;
        node.parent = tmp;
        return tmp;
    }
    /**
     * 将新元素插入树中
     */
    public insert(key: T) {
        if (this._root == null) { // [插入场景1]：红黑树是空树，新元素放到root上，其颜色置为黑色。
            this._root = new RedBlackNode<T>(key);
            this._root.color = Colors.BLACK; // 根节点要是黑色，性质2
        } else {
            const newNode = this.insertNode(this._root, key); // 插入新元素
            this.fixTreePropertiesInsert(newNode); // 新插入的元素可能导致红黑不平衡，需要处理
        }
    }
    /**
     * 将新元素插入树的哪里
     */
    protected insertNode(node: RedBlackNode<T>, key: T): RedBlackNode<T> {
        let newNode: RedBlackNode<T> = null; // 新元素
        if (this._compareFn(key, node.key) === Compare.LESS_THAN) { // key小于node.key
            if (node.left == null) {
                node.left = new RedBlackNode<T>(key);
                node.left.parent = node; // 别忘了插入后更新parent
                newNode = node.left;
            } else {
                newNode = this.insertNode(node.left, key);
            }
        } else if (this._compareFn(key, node.key) === Compare.BIGGER_THAN) { // key大于node.key
            if (node.right == null) {
                node.right = new RedBlackNode<T>(key);
                node.right.parent = node; // 别忘了插入后更新parent
                newNode = node.right;
            } else {
                newNode = this.insertNode(node.right, key);
            }
        } // 插入的值在红黑树里已经有了，对应newNode为空
        return newNode; // 返回刚插入的新元素
    }
    /**
     * 插入后的需要修复树的属性
     */
    private fixTreePropertiesInsert(node: RedBlackNode<T>) {
        // [插入场景2]：插入的元素已经存在于红黑树了，不用插入该元素。
        if (node == null) {
            return;
        }

        // [插入场景3]：新插入元素的父节点是黑色的，那么直接插入，无需进行红黑平衡。
        if (node.parent.color === Colors.BLACK) {
            return;
        }

        // [插入场景4]：新插入元素的父节点是红色，违反性质4，需要进行红黑平衡。
        this.balanceInsert(node);

        // 根节点始终保持是黑色
        this._root.color = Colors.BLACK;
    }
    /**
     * [插入场景4]：新插入元素的父节点是红色，违反性质4，需要进行红黑平衡。
     */
    private balanceInsert(node: RedBlackNode<T>) {
        let parent: RedBlackNode<T> = node.parent; // 父节点是红色
        const grandParent: RedBlackNode<T> = parent.parent; // 祖父节点肯定就是黑色
        const uncle: RedBlackNode<T> = grandParent.left === parent ? grandParent.right : grandParent.left; // 叔节点不明

        // [插入场景4.2]，叔节点存在并且为红色，对调父节点与父节点这一代的颜色
        if (uncle && uncle.color === Colors.RED) {
            parent.color = uncle.color = Colors.BLACK; // 对调父节点与父节点这一代的颜色
            grandParent.color = Colors.RED;  // 对调父节点与父节点这一代的颜色

            // 视角从node转为grandParent，因为该子树虽然平衡了但祖父节点和曾祖父节点可能都是红色，所以继续递归
            if (grandParent.parent != null && grandParent.parent.color === Colors.RED) {
                this.balanceInsert(grandParent); // 视角从node转为grandParent，然后递归
            }
            return;
        }
        // [插入场景4.1]和[插入场景4.3]，叔节点不存在或者叔节点存在但为黑色，需要旋转。旋转后就可红黑平衡
        if (grandParent.left === parent) { // 含有左-左型、左-右型两种情况
            if (parent.right === node) { // 左-右型
                // 左旋
                const tmp = this.rotationRR(parent);
                // 局部旋转后parent和node指向是相反，需要对换回来
                parent = tmp;
                node = parent.left;
            }
            // 保证右旋前后，对外暴露的顶点颜色是不变的
            this.swapColor(parent, grandParent);
            // 右旋
            this.rotationLL(grandParent);
        } else { // 含有右-右型、右-左型两种情况
            if (parent.left === node) { // 右-左型
                // 右旋
                const tmp = this.rotationLL(parent);
                // 局部旋转后parent和node指向是相反，需要对换回来
                parent = tmp;
                node = parent.right;
            }
            // 保证左旋前后，对外暴露的顶点颜色是不变的
            this.swapColor(parent, grandParent);
            // 左旋
            this.rotationRR(grandParent);
        }
    }
    /**
     * 从移除二叉搜索树中的删除一项
     */
    public remove(key: T) {
        const deleteNode: RedBlackNode<T> = this.removeNode(this._root, key);
        this.fixTreePropertiesRemove(deleteNode); // 删除黑色节点会不平衡，去平衡
        this.breakNode(deleteNode); // 删除节点
    }
    /**
     * 删除的这项，要考虑它的子节点
     * 如果它的左侧和右侧子节点同时存在就要考虑用谁来替代它原来的位置
     * 目前按照常理，找它后方最接近它的项来替代它的位置，并把“被用来替代的项”也要用removeNode删除
     */
    protected removeNode(node: RedBlackNode<T>, key: T): RedBlackNode<T> {
        let deleteNode: RedBlackNode<T> = null; // 最后一轮删除的项
        if (node == null) { // 树为空或者找不到相等值就不做任何操作（deleteNode为null）
            return deleteNode;
        }
        if (this._compareFn(key, node.key) === Compare.LESS_THAN) { // key比这个node的key小就往左边走
            deleteNode = this.removeNode(node.left, key); // 保存最后一轮删除的项
        } else if (this._compareFn(key, node.key) === Compare.BIGGER_THAN) { // key比这个node的key大就往右边走
            deleteNode = this.removeNode(node.right, key); // 保存最后一轮删除的项
        } else { // 相等
            // 没有左右侧子节点，直接删除
            if (node.right == null && node.left == null) { // 情形1
                // 它就是最后一轮要删除的项
                deleteNode =  node;
            } else if (node.right == null) { // 情形2a
                // 没有右侧子节点，而有左侧子节点，那么将左侧子节点替代它
                node.key = node.left.key; // node.left是红色并且没有后代，用node.left的值补上去
                deleteNode = node.left; // 这里deleteNode肯定是红色，删除并不会影响平衡
            } else if (node.left == null) { // 情形2b
                // 没有左侧子节点，而有右侧子节点，那么将右侧子节点替代它
                node.key = node.right.key; // node.right是红色并且没有后代，用node.left的值补上去
                deleteNode = node.right; // 这里deleteNode肯定是红色，删除并不会影响平衡
            } else { // 情形3
                /*
                 * 最特殊的情况，它有左侧子节点也有右侧子节点，删除它的话要选择合适的值替代它
                 * 删除一个值一般都是从后面寻找最接近它的项，在二叉搜索树中最接近节点的项就是它右侧节点中最小的那个
                 * 替代时，那个“被用来替代的项”也要删除，相当于用removeNode来迭代删除“被用来替代的项”
                 */
                const aux: RedBlackNode<T> = this.minNode(node.right) as RedBlackNode<T>;
                node.key = aux.key; // 只替换这个值，颜色不变。
                deleteNode = this.removeNode(node.right, aux.key); // 从右侧子节点开始删除那个“被用来替代的项”
            }
        }
        return deleteNode;
    }
    /**
     * 删除后的需要修复树的属性，从删除元素开始自底向上检查红黑平衡
     */
    private fixTreePropertiesRemove(node: RedBlackNode<T>) {
        // [删除场景1]：红黑树是空树或者找不到要删除的元素，那就无需删除
        if (node == null) {
            return;
        }

        // [删除场景2]：删除的节点是根节点或者是红色节点，那就直接删除它，无需作红黑平衡
        if (node.color === Colors.RED || node.parent == null) {
            return;
        }

        // [删除场景3]：删除的节点是黑色节点，需作红黑平衡
        this.balanceRemove(node);

        // 根节点保持黑色
        this._root.color = Colors.BLACK;
    }
    /**
     * [删除场景3]：删除的节点是黑色节点，需作红黑平衡
     */
    private balanceRemove(node: RedBlackNode<T>) {
        // 父节点
        const parent: RedBlackNode<T> = node.parent;
        // 兄弟节点
        let brother: RedBlackNode<T> = parent.left === node ? parent.right : parent.left;

        // [删除场景3.3]：其兄弟节点为红色。先旋转，再重复“场景3”的处理
        if (brother.color === Colors.RED) {
            // 旋转之前，要对调父节点和兄弟节点的颜色（保证对外暴露的顶点颜色不变）
            this.swapColor(parent, brother);
            // 删除的节点在左边，那么兄弟节点在右边
            if (parent.left === node) {
                // 左旋（兄弟节点为黑色，那么兄弟节点肯定有两个黑色子节点，直接单旋借节点给另一侧）
                this.rotationRR(parent);
            } else {
                // 右旋（兄弟节点为黑色，那么兄弟节点肯定有两个黑色子节点，直接单旋借节点给另一侧）
                this.rotationLL(parent);
            }
            // 仍不平衡，继续检查平衡，即递归一次balanceRemove
            this.balanceRemove(node);
            return;
        }
        // [删除场景3.2]：其兄弟节点为黑色，并且兄弟节点下没有子节点或者有两个黑色子节点
        if (brother.left == null && brother.right == null ||
            (brother.left != null && brother.right != null && brother.left.color === Colors.BLACK &&
             brother.right.color === Colors.BLACK)) {
            // 如果父节点为黑色，将兄弟节点变为红色，再以父节点的父节点为视角，重复“场景3”的处理。
            if (parent.color === Colors.BLACK) {
                brother.color = Colors.RED; // 将兄弟节点变为红色
                if (parent.parent != null) {// 如果父节点的父节点都不存在，那就没必要再去递归了
                    this.balanceRemove(parent); // 以父节点为视角，重复“场景3”的处理，递归
                }
            } else { // 如果父节点为红色，直接对调兄弟节点和父节点的颜色。
                this.swapColor(parent, brother);
            }
            return;
        }
        // [删除场景3.1]：其兄弟节点为黑色，并且兄弟节点有至少一个红色子节点，旋转后就可以红黑平衡
        if (parent.left === node) { // 删除的节点在左边，那么兄弟节点在右边
            if (brother.right == null || brother.right.color === Colors.BLACK) { // 右-左型，先右旋再左旋
                // 先给兄弟节点的子节点补一个黑色，以保证旋转后自身不缺黑色
                brother.left.color = Colors.BLACK;
                // 先右旋
                brother = this.rotationLL(brother); // 更新当前的兄弟节点
            } else { // 右-右型，只需左旋
                // 先给兄弟节点的子节点补一个黑色，以保证旋转后自身不缺黑色
                brother.right.color = Colors.BLACK;
            }
            // 旋转之前，要对调父节点和兄弟节点的颜色（保证对外暴露的顶点颜色不变）
            this.swapColor(parent, brother);
            // 左旋
            this.rotationRR(parent);
        } else {
            if (brother.left == null || brother.left.color === Colors.BLACK) { // 左-右型，先左旋再右旋
                // 先给兄弟节点的子节点补一个黑色，以保证旋转后自身不缺黑色
                brother.right.color = Colors.BLACK;
                // 先左旋
                brother = this.rotationRR(brother); // 更新当前的兄弟节点
            } else { // 左-左型，只需右旋
                // 先给兄弟节点的子节点补一个黑色，以保证旋转后自身不缺黑色
                brother.left.color = Colors.BLACK;
            }
            // 旋转之前，要对调父节点和兄弟节点的颜色（保证对外暴露的顶点颜色不变）
            this.swapColor(parent, brother);
            // 右旋
            this.rotationLL(parent);
        }
    }
    /**
     * 对调两个节点的颜色
     */
    private swapColor(nodeA: RedBlackNode<T>, nodeB: RedBlackNode<T>) {
        const tmpColor = nodeA.color;
        nodeA.color = nodeB.color;
        nodeB.color = tmpColor;
    }
    /**
     * 断开当前节点
     */
    private breakNode(node: RedBlackNode<T>) {
        if (node == null) {
            return;
        }
        if (node.parent != null) {
            if (node.parent.left === node) {
                node.parent.left = null;
            } else {
                node.parent.right = null;
            }
        } else {
            this._root = null;
        }
        node = null;
    }

    /**
     * 根节点
     */
    public getRoot(): RedBlackNode<T> {
        return this._root;
    }
}
